กลุ่มความซับซ้อน พี และ เอ็นพี

กลุ่มความซับซ้อน พี และ เอ็นพี ทฤษฎีความซับซ้อนในการคำนวณเป็นส่วนหนึ่งของทฤษฎีการคำนวณที่ศึกษาเกี่ยวกับทรัพยากรที่ต้องการ สำหรับการแก้ปัญหาหนึ่ง ๆ ทรัพยากรที่สนใจโดยทั่วไปคือเวลา (ต้องใช้การทำงานกี่ขั้นตอนก่อนจะแก้ปัญหาได้) และเนื้อที่ (ต้องใช้เนื้อที่เท่าใดในการแก้ปัญหา)

ในทฤษฎีดังกล่าว กลุ่ม พี (P) คือประกอบไปด้วยปัญหาการตัดสินใจที่สามารถหาคำตอบได้โดยเครื่องจักรเชิงลำดับแบบกำหนด (deterministic sequential machine) ในเวลาที่เป็นพหุนามของขนาดของข้อมูลป้อนเข้า กลุ่มปัญหา เอ็นพี (NP) ประกอบไปด้วยปัญหาการตัดสินใจที่ในกรณีที่คำตอบคือ 'ใช่' สามารถตรวจสอบได้ถ้าให้ข้อมูลที่เหมาะสม หรือพูดในอีกทางหนึ่งที่เหมือนกันว่า เป็นกลุ่มของปัญหาที่สามารถหาคำตอบได้ในเวลาพหุนามบนเครื่องจักรเชิงไม่กำหนด อาจกล่าวได้ว่าปัญหาเปิดที่สำคัญที่สุดในวิทยาการคอมพิวเตอร์เชิงทฤษฎีนั้น เกี่ยวข้องกับความสัมพันธ์ของกลุ่มปัญหาทั้งสองนี้:

ในปี 2545 มีการสำรวจความเชื่อของนักวิจัย 100 คน 61 คนเชื่อว่าพีไม่เท่ากับเอ็นพี 9 คนเชื่อว่าเท่ากัน 22 คนตอบว่าไม่แน่ใจ ส่วนที่เหลือเชื่อว่าจะไม่สามารถหาบทพิสูจน์ได้

กลุ่มของปัญหาที่อยู่ในเอ็นพีที่มีความสำคัญและได้รับความสนใจมากที่สุดก็คือกลุ่มของ เอ็นพีบริบูรณ์ ซึ่งเป็นกลุ่มของปัญหาที่ไม่น่าจะอยู่ใน พี มากที่สุด ความสัมพันธ์ของ พี เอ็นพี และ เอ็นพีบริบูรณ์ ที่นักวิจัยเชื่อกันเป็นไปตามรูป ซึ่งจะเห็นได้ว่า ทั้งพีและเอ็นพีบริบูรณ์อยู่ภายใน เอ็นพี แต่ว่าเอ็นพีบริบูรณ์กับพีไม่มีส่วนที่ซ้อนทับกันเลย อีกทั้งยังมีเซ็ตบางเซ็ตที่อยู่ในเอ็นพีแต่อยู่นอกพีและเอ็นพีบริบูรณ์

ปัญหาพีและเอ็นพีสามารถถามได้อีกแบบคือ "ถ้าเรามีปัญหาที่สามารถตรวจคำตอบ (ใช่/ ไม่ใช่) ได้อย่างรวดเร็ว เราจะสามารถหาคำตอบได้อย่างรวดเร็วหรือไม่?" ยกตัวอย่างเช่น ถ้าเราอยากตรวจสอบว่าจำนวน ๆ หนึ่งเป็นจำนวนประกอบหรือไม่ หากเรามีจำนวน 53308290611 อยู่ แล้วต้องการตรวจสอบ วิธีที่ทำได้วิธีหนึ่งก็คือทดลองจำนวนทุกจำนวนว่าหารจำนวนนี้ลงตัวหรือไม่ แต่วิธีนี้ใช้เวลาการทำงานเป็น exponential เมื่อเทียบกับขนาดของอินพุต (ขนาดของอินพุตในที่นี้ไม่ใช่ค่าของจำนวน แต่เป็นจำนวนของบิตที่ใช้ในการแทนค่าจำนวนนั้น ยกตัวอย่างเช่น จำนวน 128 มีขนาดของอินพุตเท่ากับ 8 เพราะว่า 128 = 10000000 2 {\displaystyle 128={10000000}_{2}} )